import java.util.ArrayList;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-10-14
 * Time: 18:28
 */
public class MyStack {
    public boolean isValid(String s){
        int i = 0;
        char ch = 0;
        Stack<Character> stack=new Stack<>();
        for (i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            }else {
                break;
            }
        }
        for (int j = i; j < s.length(); j++) {
            ch = s.charAt(j);
            char brackets=stack.peek();
            if(stack.isEmpty()){
                return false;
            }
            if(brackets == '(' && ch == ')' || brackets == '{' && ch =='}' || brackets == '[' && ch ==']'){
                stack.pop();
            }
        }
        if(!stack.isEmpty()){
            return false;
        }
        return true;
    }

    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k){
        ArrayList<Integer> list=new ArrayList<>();
        heapSort(input);
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }
        return list;
    }

    public void siftDown(int[] array,int parent,int end){//建大根堆
        int child=2*parent+1;
        while(child < end){
            if(child+1 < end && array[child] < array[child+1]){
                child++;
            }
            if(array[child] >= array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }
    public void createHeap(int[] array){
        int parent=(array.length-1-1)/2;
        for (int i = parent; i >= 0; i--) {
            siftDown(array,i,array.length);
        }
    }
    public void heapSort(int[] array){
        int end=array.length-1;
        createHeap(array);
        while(end > 0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }
    private void swap(int[] array,int a,int b){
        int tmp=array[a];
        array[a]=array[b];
        array[b]=tmp;
    }
}
